Brojevi Katalana 
Vrsta: Seminarski | Broj strana: 28 | Nivo: Fakultet tehničkih nauka Novi Pazar

Sadržaj:
1. Uvod
n
Cn
n
Cn
n
Cn
n
Cn
1
1
7
429
13 742,900
19
1,767,263,190
2
2
8
1,430
14
2,674,440
20
6,564,120,420
3
5
9
4,862
15
9,694,845
21
24,466,267,020
4
14
10
16,796
16
35,357,670
22
91,482,563,640
5
42
11
58,786
17
129,644,790
23
343,059,613,650
6
132
12
208,012
18
477,638,700
24
1,289,904,147,324
Tablica 1:
Catalanovi brojevi
2. Problemi vezani uz Catalanove brojeve
2.1 Triangulacija konveksnog n-terokuta
Ovaj povijesno najstariji problem doveo je do otkrića Catalanovih brojeva. Razmatra se broj načina (označimo taj broj s Tn) na koji je moguća maksimalna dekompozicija konveksnog n-terokuta na n-2trokuta (otud ime triangulacija). Da bismo ga triangulirali, potrebno je povući n-3 dijagonala koje se ne smiju sjeći. Ako vam ovo nije odmah očito, jedna dijagonala dijeli ga na dva dijela, dvije na tri i tako dalje indukcijom po n.
Razmotrimo problem induktivno i počnimo s trokutom. S obzirom da je on već trianguliran, postoji samo jedan način triangulacije pa je stoga T3 = 1. Za konveksan četverokut (n = 4) moramo povući jednu dijagonalu. To možemo učiniti na dva načina (jer takav četverokut ima dvije dijagonale) pa je, dakle, T4 = 2. Za peterokut (n = 5) rješenje je manje očigledno, postoji 5 načina triangulacije. Nađimo sad opće rješenje za broj triangulacija n-terokuta Tn. Primijetimo da je svaka stranica n-terokuta dio točno jednog trokuta triangulacije.
Za prebrojavanje koristit ćemo rekurziju i sljedeći algoritam - nasumce odabiremo i fiksiramo jednu od stranica te brojimo triangulacije u kojima sudjeluje svaki od trokuta podignutih nad tom stranicom. Za k-tu točku kao vrh trokuta, zdesna je ostao (n - k + 1)-terokut, koji možemo triangulirati na Tn-k+1 načina, a s lijeva k-terokut koji možemo triangulirati na Tk načina (vidi sliku 1). Pritom podrazumijevamo da jeT2 = 1.

---------- OSTATAK TEKSTA NIJE PRIKAZAN. CEO RAD MOŽETE PREUZETI NA SAJTU. ---------- 

www.maturskiradovi.net 

 

MOŽETE NAS KONTAKTIRATI NA E-MAIL: maturskiradovi.net@gmail.com